package sort;

import java.util.Arrays;

/**
 * @Author leecho
 * @Date: 2021/10/19 11:32
 * @Version 1.0
 */

public class InsertSort {
    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
        int[] arr ={34,101,1,25};
        insertSort.insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /*
    * 思路
    * - 将每一个数字与数组中的剩下的数字进行比较判断
    *   - 大于继续往前走
    *   - 小于放在当前移动到的位置
    * - 不符合的数字会整体后移，找到位置放入后，数组中的元素没有发生改变
    * */
    public void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int index = i-1;
            while (index >= 0 && temp < arr[index] ){
                arr[index+1] = arr[index];
                index--;
            }
            arr[index+1] = temp;
        }
    }

}
